제4장 재귀 호출
- 제4장 재귀 호출
- 4.2. 재귀 함수를 비재귀 함수로 바꾸기
- 문서에 대하여
4.2. 재귀 함수를 비재귀 함수로 바꾸기
- 1. 재귀호출은 알고리즘에 대해 직관적이지만,
- 비재귀함수에 비해 느리고, --> 속도를 요하는 작업이면 비재귀로 사용하자.
- 함수를 호출하기 위한 오버헤드가 있다.
- 2. 재귀호출은 시스템 다운의 우려가 있다.
- 자신을 수없이 많이 호출하기 때문이다. (C언어에서는 오버플로우를 따로 체크하지않기때문에..)
- 위의 이유로 재귀함수는 프로그램의 초기단계에서는 애용되지만 프로그래밍 최종단계(최적화)에서는 비재귀 함수로 변환한다.
4.2.1. 재귀 호출이 하나인 경우
public class Factorial2 {
/**
* 누승을 구함.
* @param n
* @return
*/
public static int factorial(int n) {
//if(n == 0)
if(n < 1) // 방어적 프로그래밍
return 1;
else
return n * factorial(n - 1);
}
/**
* Trace용 누승을 구함.
* @param n
* @return
*/
private static int tab = 0;
public static int traceFactorial(int n) {
String debug = "factorial(" + n + ") -----> ";
if(n < 1) {
printTab(debug + "return 1\r\n");
return 1;
}
else {
printTab(debug + "return " + n + " * " + "factorial(" + (n-1) + ")");
return n * traceFactorial(n - 1);
}
}
private static void printTab(String message) {
for(int i=0; i<tab; i++) {
System.out.print("\t");
}
System.out.println(message);
tab++;
}
/**
* 비재귀를 사용한 누승을 구함.
* @param n
* @return
*/
public static int iter_factorial(int n) {
int f = 1;
while(n > 0)
f = f *n--;
return f;
}
// MAIN
public static void main(String[] args) {
System.out.println(factorial(5));
System.out.println(iter_factorial(5));
/**
* factorial(5) : 120
* iter_factorial(5) : 120
*/
}
}
결과:
factorial(5) : 120
iter_factorial(5) : 120
4.2.2. 재귀 호출이 둘인 경우 - 1
- 경우의 수가 세가지 있다.
- 첫째. process함수가 두 재귀호출의 앞에 나와있는 경우.
/**
* 유형 1
*/
recursive(인자리스트) {
if(종료조건) {
종료 처리;
}
else {
// 종료조건이 아니면.
process(인자리스트);
recursive(변경된인자1);
recursive(변경된인자2);
}
}
/**
* 유형1 _비재귀판.
*/
non_recursive(인자리스트) {
init_stack(); // 스택초기화.
push(인자리스트);
while(!is_stack_emtpty()){ // 스택이 비면 끝.
인자리스트 = pop();
if(!종료조건) { // 종료조건이 아니면.
process(인자리스트);
push(변경된인자2);
push(변경된인자1);
}
else { // 종료 조건이면.
종료 처리;
}
}
}
- 트리의 preorder_traverse 경우,
/**
* 트리의_순환중_뿌리노드부터_검색.
* @param t 트리 노드
*/
void preorder_traverse(Node t) {
if(t != tail) {
visit(t);
preorder_traverse(t.left);
preorder_traverse(t.right);
}
}
/**
* 트리의_순환중_뿌리노드부터_검색.(비재귀)
* @param t 트리 노드
*/
void preorder_traverse(Node t) {
init_stack();
push(t);
while(!is_stack_empty()) {
t = pop();
if(t != tail) {
visit(t);
push(t.right);
push(t.left);
}
}
}
/**
* 트리의_순환중_뿌리노드부터_검색.(비재귀, 자바코드)
* @param t 트리 노드
*/
void preorder_traverse(Node t) {
Stack<Node> stack = new Stack<Node>();
stack.push(t);
while(!stack.isEmpty()) {
t = stack.pop();
if(t.equals(tail)) {
visit(t);
stack.push(t.right);
stack.push(t.left);
}
}
}
| <유형1> | preorder_traverse() |
| 인자 리스트 | t |
| 종료 조건 | t.equals(tail) |
| 종료 처리 | 없음 |
| process() | visit() |
| 변환된 인자1 | t.left |
| 변환된 인자2 | t.right |
4.2.3. 재귀 호출이 둘인 경우 - 2
- 둘째. process함수가 두 재귀호출의 사이에 있는 경우.
/**
* 유형 2
*/
recursive(인자리스트) {
if(종료조건) {
종료 처리;
}
else {
// 종료조건이 아니면.
recursive(변경된인자1);
process(인자리스트);
recursive(변경된인자2);
}
}
/**
* 유형2 _비재귀판.
*/
non_recursive(인자리스트) {
int done = 0; // 작업을 완료했는지의 플래그.
init_stack(); // 스택초기화.
while(!done) {
while(!종료 조건){ // 스택이 비면 끝.
push(인자리스트 );
인자리스트 =변환된인자1;
}
종료 처리;
if(!is_stack_empty()) { // 종료조건이 아니면.
인자리스트 = pop();
process(인자리스트);
인자리스트 = 변경된인자2;
}
else {
done = 1;
}
}
}
/**
* 트리의_순환중_중간노드부터_검색.
* @param t 트리 노드
*/
void inorder_traverse(Node t) {
if(t != tail) {
inorder_traverse(t.left);
visit(t);
inorder_traverse(t.right);
}
}
/**
* 트리의_순환중_중간노드부터_검색. (비재귀)
* @param t 트리 노드
*/
void inorder_traverse(Node t) {
int done = 0;
init_stack();
while(!done) {
while(t != tail) { // 종료조건이 아니면.
push(t); // 인자리스트를 푸쉬.
t = t.left; // 인자리스트 = 변경된 인자1
}
if(!is_stack_empty()) {
t = pop(); // 인자리스트 = pop();
visit(t); // process()
t = t.right; // 인자리스트 = 변경된 인자2
}
else {
done = 1;
}
}
}
/**
* 트리의_순환중_중간노드부터_검색. (비재귀, 자바)
* @param t 트리 노드
*/
void inorder_traverse(Node t) {
boolean done = false;
Stack<Node> stack = new Stack<Node>();
while(!done) {
while(t.equals(tail)) { // 종료조건이 아니면.
stack.push(t); // 인자리스트를 푸쉬.
t = t.left; // 인자리스트 = 변경된 인자1
}
if(!stack.isEmpty()) {
t = stack.pop(); // 인자리스트 = pop();
visit(t); // process()
t = t.right; // 인자리스트 = 변경된 인자2
}
else {
done = true;
}
}
}
4.2.4. 재귀 호출이 둘인 경우 - 3
- 셋째. process함수가 두 재귀호출 뒤에 있는 경우.
/**
* 유형3
*/
recursive(인자리스트) {
if(종료조건) {
종료 처리;
}
else {
// 종료조건이 아니면.
recursive(변경된 인자1);
recursive(변경된인자2);
process(인자리스트);
}
}
/**
* 유형3 _비재귀판.
*/
non_recursive(인자리스트) {
int done = 0; // 작업을 완료했는지의 플래그.
인자리스트 복사본; // 무한루프를 방지하기 위한 방책.
init_stack(); // 스택초기화.
while(!done) {
while(!종료 조건){ // 스택이 비면 끝.
push(인자리스트 );
인자리스트 =변환된인자1;
}
종료 처리;
if(!is_stack_empty()) {
인자리스트의 복사본 =인자리스트;
인자리스트 = pop();
if(인자2로의 _변화가_종료조건이_아니면) {
if(인자2로의_변화==인자리스트의_복사본) {
process(인자리스트);
}
else {
push(인자리스트);
인자리스트 = 변경된인자2;
break;
}
}
else {
process(인자리스트);
}
}
if(!is_stack_empty()) {
done = 1;
}
}
}
4.2.5. 그 외의 경우
/**
* 유형4
*/
recursive(인자리스트) {
if(종료조건) {
종료 처리;
}
else {
// 종료조건이 아니면.
process(인자리스트);
recursive(변경된 인자1);
recursive(변경된인자2);
recursive(변경된인자3);
.
.
.
recursive(변경된인자N);
}
}
/**
* 유형4 _비재귀판.
*/
non_recursive(인자리스트) {
init_stack(); // 스택초기화.
push(인자리스트 );
while(!is_stack_empty()) {
인자리스트 = pop();
if(!종료조건) {
process(인자리스트);
push(변경된인자N);
.
.
.
push(변경된인자3);
push(변경된인자2);
push(변경된인자1);
}
else {
종료처리;
}
}
}
4.2.6. 새로운 접근 방법으로 비재귀판을 만드는 경우
/**
* 재귀함수를 _사용한_피보나치
* @param n
* @return
*/
public static int fibonacci(int n) {
if((n == 1) || (n == 2))
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
/**
* 재귀함수를_사용한_피보나치와_전혀_다른 _함수.
* @param n
* @return
*/
public static int iter_fibonacci(int n) {
int r = 0;
int a = 1, b = 1;
if((n == 1) || (n == 2))
return 1;
while(n-- > 2) {
r = a + b; // 값 교환에 의해 피보나치 수 구함.
a = b;
b = r;
}
return r;
}
4.2.7. 주의점
- 1. 비재귀함수는 항상 재귀함수보다 빠른건 아니다. (비재귀함수도 호출이 많아지면 느려진다.)
- 2. 함수오버플로우 문제도 제어할 수 있다.(스택 오버플로우의 경우는 스택 MAX값을 크게 잡으면 된다.
문서에 대하여
- 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
- 최초작성자 : 장선웅
- 최초작성일 : 2009년 3월 13일
- 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
- 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^